#include <vector>
#include <algorithm>

using namespace std;

int maxSum(const vector<int> &array) {
  vector<vector<int>> maxNumbers(array.size(), {0});

  if (array.size() == 0) {
    return 0;
  }
  else if (array.size() == 1) {
    maxNumbers.push_back({array[0]});
    return array[0];
  }

  vector<int> sum = array;
  sum[1] = max(array[0], array[1]);
  maxNumbers[0] = {array[0]};
  maxNumbers[1] = {sum[1]};

  for (int i = 2; i < array.size(); ++i) {
    int prev = sum[i - 1];
    int curr = sum[i - 2] + array[i];

    if (curr <= prev) {
      maxNumbers[i] = maxNumbers[i - 1];
      sum[i] = prev;
    }
    else {
      auto tmp = maxNumbers[i - 2];
      tmp.push_back(array[i]);
      maxNumbers[i] = tmp;
      sum[i] = curr;
    }

    // sum[i] = max(sum[i - 1], sum[i - 2] + array[i]);
  }

  return *sum.rbegin();
}

int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
